Везде, где не оговорено обратное, речь идёт про конечные графы. Существуют также бесконечные, не все определения для них сохраняются
Граф
Граф:
| --- | Ориентированный | Неориентированный |
|---|---|---|
| Без кратных рёбер и петель | Отношение |
|
| С кратными рёбрами и петлями | Это означает, что в одну и ту же пару Пара |
Отношение |
Отображения, аналогичные тем, что даны для графов с кратными рёбрами, можно дать и для графов без кратных рёбер. В данном случае это будет означать, что отображение инъективно (каждой паре вершин соответствует ровно одно ребро, тогда как для графа с кратными рёбрами одной паре может соответствовать несколько рёбер)
Подграф
Примеры операций над графами, создающих подграфы:
Инцидентность
Пара вершина-ребро
Степень вершины
Степенью (или порядком) вершины называется количество рёбер, инцидентных с вершиной.
Смежность
Окрестность
Подграф
Висячая вершина
Это вершина со степенью 1
Дополнительный граф
Рассмотрим граф
Путь на графе
Пусть
Тогда путь на графе - это последовательность невырожденных рёбер
| Для орграфа | Для неорграфа |
|---|---|
| Последовательность вершин Соответствующая ей последовательность рёбер |
Путь длины ноль ведёт из вершины в неё саму
Цепь - путь, в котором рёбра не повторяются
Простая цепь, она же простой путь - путь, в котором не повторяются рёбра и вершины
"Определение"
Цикл - простая замкнутая цепь (то есть
Теорема (без доква)
Если между вершинами есть путь, то они соединены простой цепью
Пояснение
На самом деле это достаточно простой факт. Он основан на том, что любой цикл можно просто удалить
Отношение достижимости
Путь на графе определяет отношение достижимости: это означает, что существует путь между двумя вершинами
Отношение достижимости на орграфе является отношением предпорядка:
Отношение нестрогого порядка (
Отношение предпорядка: рефлексивное, транзитивное
Пусть
То есть
Матрица инцидентности для ографа
I(G), где G -- орграф. Матрица размера VxE (столбцы -- рёбра, строчки -- вершины) в которой (v,e) равна:
На неорграфе можно ввести ориентацию, потому что каждое ребро это технически два орребра
Для неорграфа часто считают, что компоненты берутся по модулю 2 (то есть -1 становится 1, то есть знак перестаёт влиять)
Матрица смежности
А(G) квадратная матрица VxV.
Теорема
Для неорграфа без петель
Её компонента
Также замечание: симметричная матрица, возведённая в степень, останется симметричной, поэтому
Доказательство
Индукция по q.
Матрица Кирхгофа
Иное название - Лапласиан графа.
Рассмотрим теперь
Лемма о рукопожатиях (для неорграфа)
Рассмотрим множество
Следствие
Количество вершин нечётной степени в любом графе чётно
Пояснения
Иначе бы получилось, что
Рассмотрим неориентированный граф
Определения дерева и леса
Ряд сведений о деревьях
Предложение
Теорема
В дереве с
Доказательство
Ранг графа
Число
Пояснение
Матрица инцидентности строится относительно некоторой ориентации. В случае неографа ориентация может быть задана произвольно
Теорема
При этом каждый блок является
3. [вариант док-ва от препода]. Докажем, что у любого дерева есть вершина степени 1, а если в нём есть рёбра, то их по крайней мере две. Для этого достаточно рассмотреть максимальный простой путь на данной графе. Если степень вершины не 1, то путь можно удлинить. Иначе степень равна 1. В итоге можно будет рассмотреть матрицы (при выкидывании висячей вершины связность не нарушается, используем ММИ):
\begin{CD}
x_0 @= x_1 @= x_2 @=x_3\
@| @| @| @| \
x_4 @= x_5 @= x_6 @= x_7\
@.@|@|@.\
@.x_8@=x_9
\end{CD}$$
Цикломатическое число равно трём, хотя количество циклов гораздо больше
Эйлеров путь -- это путь, проходящий по всем рёбрам графа ровно один раз
Эйлеров цикл -- это замкнутый путь, который проходит через каждое ребро графа по одному разу.
Граф, в котором существует Эйлеров цикл, называется Эйлеровым графом
Полуэйлеров граф -- граф, в котором существует эйлеров путь
Лемма
Если в графе степень каждой вершины чётна, то начиная с любого ребра можно начать цикл, который проходит через каждое ребро единожды (но может несколько раз пройти через вершину).
Доказательство
Теорема
Следствие (тривиальное)
Если граф несвязный, а все вершины имеют чётную степень, то это объединение непересекающихся эйлеровых циклов
Теорема
Рассматриваем связные графы
Произвольно вычерчиваемый граф
Эйлеров граф
Пример
Произвольно вычерчиваемый из
Не произвольно вычерчиваемый из
Предложение
Граф
Ещё один вариант определения: граф называется двудольным, если у него существует правильная раскраска в два цвета: вершины можно раскрасить в два цвета так, чтобы две вершины одного цвета не были смежными.
А если можно правильно раскрасить в k цветов, то есть покрасив в k цветов не получить рядом вершины одного цвета, то этот граф называется k-дольным
Критерий двудольности графа
Два графа
Важным признаком неизоморфности графов являются отличающиеся степени его вершин. Однако вполне могут существовать графы на вершинах с одинаковыми степенями, но не изоморфные друг другу
Ещё одним способом определять изоморфность графов: теорема Уитни
Точка сочленения
Пояснение
Вершина со степенью ноль не является ТС
Предложение
Тривиально. (=>) раз кол-во увеличилось, то есть такие точки, что связаны только через
(<=) Если это не ТС, то кол-во КС не должно увеличиться. Однако после удаления больше не будет путей. То есть увеличится
Замечание
В дереве любая не висячая вершина есть точка сочленения
Доказательство
Очевидно
Замечание
Любая точка цикла не является ТС
Доказательство
Очевидно
Блок
Блок -- максимальный по включению (по количеству точек, рёбра остаются теми же, что в изначальном графе) связный подграф без точек сочленения.
Пояснение
В этом графе ТС являются
Замечание
В блоке с
Доказательство (смотри пояснение)
Предложение
В блоке:
Теорема
Дерево блоков и точек сочленения
Рассмотрим граф, в котором остаются лишь блоки, которые связаны со своими точками сочленения
Определение Пусть G связен. Обозначим
Пояснение Почему дерево?
Висячий блок
Блок называется висячим, если в нём содержится ровно одна точка сочленения исходного графа
Пояснение
Предложение
В связном графе:
Код Прюфера
Перед доказательством следующей теоремы рассмотрим конструкцию Кода Прюфера. Код Прюфера сопоставляет произвольному конечному дереву с n вершинами последовательность из
Теорема (Кэли)
Число деревьев с
Доказательство
Теорема Бине-Коши (без доказательства)
Рассмотрим произведение двух прямоугольных матриц
Доказательство
Матричная теорема о деревьях
Рассмотрим связный граф
Доказательство
Гамильтонов путь
Путь, проходящий через каждую вершину по одному разу называется гамильтоновым.
Аналогично даётся определение гамильтонова цикла
Замечание
Предложение
В полуполном орграфе существует гамильтонов путь
Доказательство
Теорема Оре (Билет 15)(Достаточное условие существования гамильтонова цикла на неорграфе)
Если в графе есть несмежные вершины и для любых двух из них
Доказательство
В теории графов используется такой объект, как корневые деревья. Одна вершина дерева объявляется корнем, после чего все рёбра ориентируются в направлении “от корня”. Один из видовых таких деревьев - DFS-деревья или деревья поиска в глубину.
Пояснение
Алгоритм построения DFS-Tree
Нумеруем вершины
0. Начинаем с произвольной вершины (её номер - 1)
Утверждение (тривиальное)
При обходе в глубину будут включены все вершины исходного графа
Прямые и обратные рёбра
Запустим DFS из произвольной вершины. Введем новые виды рёбер:
Продольные и поперечные рёбра
Обратные рёбра можно разделить на две категории.
На показанном ниже рисунке потенциальным поперечным ребром могло бы быть ребро
Утверждение
В дереве поиска в глубину нет поперечных рёбер
Доказательство
Замечание (Это уже следующий билет - 12)
Построение DFS-дерева задаёт функцию-нумерование вершин этого дерева. Обозначим её
Одновременно с этим можно определить функцию
Предложение (Билет 13)
Поиск
“Pasted image 20240420021726.png” не может быть найдена.
НА КАРТИНКЕ СЛОМАНА НУМЕРАЦИЯ, СМОТРИ НА СТРЕЛКИ!
Теорема
Введём функцию высоты. Корень дерева имеет высоту 0, каждая дочерняя вершина имеет высоту на 1 больше, чем родительская.
Тогда
Доказательство
k-связный граф
Лемма (к т.Брукса)
Раскраска графа
Хроматическое число графа
Теорема
Теорема (Брукса)
Плоский граф
В рамках данного параграфа
Теорема (формула Эйлера)
Замечание (следствие формулы Эйлера)
Лемма (о перекрашивании вершин)
Теорема о пяти красках
Доказательство
Независимость вершин графа
Паросочетания
Вершинное покрытие
Рёберное покрытие
Свойства чисел
#TODO
При рассказе про паросочетания:
Лемма 4.1. Для любого графа G выполняется неравенство
χ(G) · α(G) ≥ v(G).
Доказательство. Утверждение очевидно следует из соображения о том,
что все вершины одного цвета в правильной раскраске попарно несмежны, то есть образуют независимое множество.
Чередующийся путь
Утверждение
Если в графе есть максимальный по включению простой чередующийся путь, концы которого не принадлежат паросочетанию, то паросочетание не максимальное
Доказательство
Теорема Бержа (о максимальном паросочетании в произвольном графе) (Билет 20)
Теорема Кёнига (Билет 22)
Теорема Холла (Билет 23)
Доказательство
Совершенное паросочетание
Утверждение
Доказательство
Следствие
Частично упорядоченное множество
Теорема (Дилуороса)
Хроматическое число графа (напоминание)
Хроматический многочлен
Существование хроматического многочлена
Утверждение
Утверждение
Рёберная раскраска
Покрывающая раскраска
Оптимальная раскраска
Лемма
Лемма (об оптимальной раскраске в два цвета)
Теорема (Кёнига, о хроматическом индексе двудольного графа)
Теорема Гупта